package demo.hw;

import java.util.ArrayList;
import java.util.List;

public class _最富裕的小家庭 {
    public static void main(String[] args) {
        /**
         *在一颗树中，每个节点代表一个家庭成员，节点的数字表示其个人的财富值，一个节点及其直接相连的子节点被定义为个小家庭。
         * 现给你一颗树，请计算出最富裕的小家庭的财富和。
         * 输入描述
         * 第一行为一个数N，表示成员总数，成员编号1~N。1<N1000
         * 第二行为N个空格分隔的数，表示编号1~N的成员的财富值。0<=财富值<=1000000.
         * 接下来N-1行，每行两个空格分隔的整数（N1,N2），表示N1是N2的父节点Q
         * 输出描述
         * 最富裕的小家庭的财富和
         * 示例1：
         * 输入：
         * 4
         * 100 200 300 500
         * 1 2
         * 1 3
         * 2 4
         * 输出
         * 700
         * 说明
         * 成员1,2,3组成的小家庭财富值为600成员
         * 2,4组成的小家庭富值为700
         */
        int N = 4;
        int[] wealth = {0, 100, 200, 300, 500}; // 索引0不用,从1开始
        int[][] relation = {
                {1, 2},
                {1, 3},
                {2, 4}
        };
        // 构建父树结构 数组+列表
        List<Integer>[] families = new ArrayList[N + 1];// 从1开始,故N+1
        for (int i = 1; i <= N; i++) {
            families[i] = new ArrayList<>();
        }
        // 构建父子关系
        for (int i = 0; i < relation.length; i++) {
            int parent = relation[i][0];
            int child = relation[i][1];
            families[parent].add(child);
        }

        // 小家庭财富 = 父节点财富+所有子节点财富
        int max = 0;
        for (int i = 1; i <= N; i++) {
            // 父节点财富
            int familyWealth = wealth[i];

            // 加上所有直接子节点的财富
            for (int child : families[i]) {
                familyWealth += wealth[child];
            }
            max = Math.max(max, familyWealth);
        }
        System.out.println(max);
    }
}
